import  java.util.*;
import java.lang.String;

class Strings {

    //newcode CC219子串判断
    //给定一个string数组p及其大小n，同时给定长字符串string s，请返回一个bool数组，元素为true或false对应p中的对应字符串是否为s的子串。
    public boolean[] chkSubStr(String[] p, int n, String s) {
        boolean[] bool = new boolean[n];
        for (int i = 0; i < n; i++) {
            bool[i] = s.contains(p[i]);
        }
        return bool;
    }


    //newcode CC161 翻转子串
    //判断s2是否由s1翻转得来
//    public boolean checkReverseEqual(String s1, String s2) {
//        // write code here
//        if (s1.length() != s2.length())
//            return false;
//        String str = s1.append(s1);//把s1后追加s1，如果是翻转而来，s2一定是str的子串
//        return str.contains(s2);//是否为子串
//
//    }


    //newcode CC228 合法括号序列判断
    public boolean chkParenthesis(String A, int n) {
        //同理NC52
        if (n % 2 != 0)
            return false;
        Stack<Character> st = new Stack<>();
        for (int i : A.toCharArray()) {
            if (i == '(') {
                st.push('(');//把左括号存起来
            } else if (i == ')') {
                if (st.empty())//当右括号但栈为空，一定不合法
                    return false;
                st.pop();//删除对应左括号
            } else {
                return false;
            }
        }
        return st.empty();
    }

    //newcode NC52 有效的括号序列
    public boolean isValid(String s) {
        if (s == null)
            return false;
        Stack<Character> st = new Stack<>();
        for (int ch : s.toCharArray()) {
            //当为左括号，向栈中存右括号
            if (ch == '(')
                st.push(')');
            else if (ch == '[')
                st.push(']');
            else if (ch == '{')
                st.push('}');
            else//当为右括号判断此时是否对应
                if (st.empty() || st.pop() != ch)//当为空返回f，当栈顶值不为对应的括号返回f
                    return false;
        }
        return st.empty();//如果此时为空
    }

    //newcode CC210 词频统计
    public int getFrequency(String[] article, int n, String word) {
        int num = 0;
        for (int i = 0; i < n; i++) {
            //直接对比word与该字符串数组的每项
            if (article[i].equals(word)) {
                num++;
            }
        }
        return num;
    }
}